/*
 * @lc app=leetcode.cn id=629 lang=typescript
 *
 * [629] K个逆序对数组
 */

// @lc code=start
function kInversePairs(n: number, k: number): number {
  const MOD = 1000000007;
  // dp[i][j] 表示前i个数中，逆序对的个数为j的情况下，最小的值
  // 滚动数组
  const f = new Array(2).fill(0).map(() => new Array(k + 1).fill(0));
  f[0][0] = 1;
  for (let i = 1; i <= n; ++i) {
    for (let j = 0; j <= k; ++j) {
      const cur = i & 1,
        prev = cur ^ 1;
      f[cur][j] = (j - 1 >= 0 ? f[cur][j - 1] : 0) - (j - i >= 0 ? f[prev][j - i] : 0) + f[prev][j];
      f[cur][j] = f[cur][j] < 0 ? f[cur][j] + MOD : f[cur][j] % MOD;
    }
  }
  return f[n & 1][k];
}
// @lc code=end
